package com.leetcode.August;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 22括号生成
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-12 20:10
 */
public class LC22括号生成 {
    //    private char[] path;
//    private List<String> res = new ArrayList<>();
//
//    public List<String> generateParenthesis(int n) {
//        int m = n * 2;
//        path = new char[m];
//        dfs(0, 0, m, n);
//        return res;
//    }
//
//    private void dfs(int open, int i, int m, int n) {
//        if (i == m) {
//            res.add(new String(path));
//            return;
//        } else if (open < n) {
//            path[i] = '(';
//            dfs(open + 1, i + 1, m, n);
//        } else if (i - open < open) {
//            path[i] = ')';
//            dfs(open, i + 1, m, n);
//        }
//    }\
    private char[] path;
    private List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        int m = n * 2;
        path = new char[m];
        dfs(0, 0, m, n);
        return res;
    }
//i当前正在构建的括号字符串的位置 open左括号数量
    private void dfs(int open, int i, int m, int n) {
        if(i==m){
            res.add(new String(path));
            return;
        };
        if (open < n){
            path[i]='(';
            dfs(open+1,i+1,m,n);
        } ;
        if (i-open<open) {//左括号数量 open 大于当前字符串中右括号的数量 i - open
             path[i] = ')';
             dfs(open, i + 1, m, n);
        }
    }
}
